package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Scanner;

/*
数字三角形(POJ1163)

在数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。
路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可，不必给出具体路径。

三角形的行数大于1小于等于100，数字为 0 - 99

输入格式：
in
5		
7  
3 8
8 1 0
2 7 4 4
4 5 2 6 5

out
30
要求输出最大和


 */

public class h数字三角形最大路径值byDP {
	public static void main(String[] args) {
		h数字三角形最大路径值byDP test = new h数字三角形最大路径值byDP();
		test.useDP();
	}
	
	/**
	 * 前置方法
	 */
	public void useDP() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int[][] triangle = new int[N][];
		for (int i = 0; i < N; i++) {
			triangle[i] = new int[i + 1];
			for (int j = 0; j < i + 1; j++) {
				triangle[i][j] = scanner.nextInt();
			}
		}
		int column = triangle[N - 1].length;
		int[] dp = new int[column];//dp只需要一维数组即可；因为可以一直覆盖
		for (int i = 0; i < column; i++) {
			dp[i] = triangle[N - 1][i];
		}
		int res = DP(N, triangle, 0, 0, dp);
		System.out.println(res);
	}
	
	/**
动态规划
自底向上
dp方程是=
	res[i][j] = triangle[i][j] + Math.max(res[i+1][j],res[i+1][j+1]);操作指的是：
		triangle[i][j] + Math.max(res[i+1][j],res[i+1][j+1]);即原三角中的当前元素 + 它两个孩子的最大的
	res是一个与triangle完全相似但是元素全为0的空三角
	但是理论上不需要创建一个res；创建这样的res会浪费空间，因为我们又不关心过程
	
	所以我们可以只创建一个一维数组来保存每一行的操作结果。新的结果会覆盖旧的。
	这样即实现了目的，也节省了空间。
	 * @param N
	 * @param triangle
	 * @param row
	 * @param col
	 * @param dp
	 * @return
	 */
	public int DP(int N, int[][] triangle, int row, int col, int dp[]) {
		for (int i = N - 2; i >= 0; i--) {//模拟需要被填入的行；永远是已填好的行的上一行；所以初始值是N-2
			for (int j = 0; j <= i; j++) {//遍历已填好的行的指针；所以从1开始
				dp[j] = triangle[i][j] + Math.max(dp[j], dp[j + 1]);//存入dp；也是覆盖旧数据
			}
		}
		return dp[0];
	}
}
